/*
 * @lc app=leetcode.cn id=57 lang=javascript
 *
 * [57] 插入区间
 */

// @lc code=start
/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function (intervals, newInterval) {
  const res = [];
  const n = intervals.length;
  let i = 0;
  // 左侧不重叠区间加入
  while (i < n && intervals[i][1] < newInterval[0]) {
    res.push(intervals[i]);
    i++;
  }
  // 重叠情况，新区间只有比区间开头大才能继续合并，用新区间存范围后push即可
  while (i < n && newInterval[1] >= intervals[i][0]) {
    newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
    newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
    i++;
  }
  res.push(newInterval);

  // 右侧不重叠区间
  while (i < n) {
    res.push(intervals[i]);
    i++;
  }
  return res;
};
// @lc code=end
